package demo3;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-02
 * Time: 16:20
 */
public class TestDemo {



    public static int merge(int[] array,int left,int mid,int right){
          int b1 = left;
          int b2 = mid+1;
          //先进行计算在归并
          int ans =0;
          int windowR = mid+1;
          for(int i=b1;i<=mid;++i){
              // 3  3  4        1  1 2
              //对于每一个数要找到在右组*2倍都没有这个数大的数字
              while(windowR<=right&&array[i]>2*array[windowR]){
                  windowR++;
              }
              ans += windowR - mid-1;
          }
          //接下来进行归并过程
          int[] tmp = new int[right-left+1];
          int k =0;
          while(b1<=mid&&b2<=right){
              tmp[k++] = array[b1]<=array[b2]? array[b1++]: array[b2++];
          }
          while(b1<=mid){
              tmp[k++] = array[b1++];
          }
          while(b2<=right){
              tmp[k++] = array[b2++];
          }
          for(int i =0;i<tmp.length;++i){
              array[left+i] = tmp[i];
          }
          return ans;
    }

    public static int process(int[] array,int left,int right){
        if(left>=right) return 0;
        int mid = left+((right-left)>>>1);
        return process(array,left,mid)+
                process(array,mid+1,right)+
                merge(array,left,mid,right);
    }


    public static int BiggerThanRightTwice(int[] array){
        return process(array,0,array.length-1);
    }


    //找一个数的后面有多少*2都没有本身大的数字
    public static int func(int[] arr){
        int cnt =0;
        for(int i =0;i<arr.length;++i){
            for(int j = i+1;j<arr.length;++j){
                if((arr[j]*2)<arr[i]){
                    ++cnt;
                }
            }
        }
        return cnt;
    }

    public static int[] copyArray(int[] arr){
        int[] arr1 = new int[arr.length];
        for(int i =0;i<arr.length;++i){
            arr1[i] = arr[i];
        }
        return arr1;
    }

    public static int[] generateRandomArray1(int maxSize,int maxValue){
        int[] arr = new int[(int)((maxSize+1)*Math.random())];
        for(int i =0;i<arr.length;++i){
            arr[i] = (int)((maxValue+1)*Math.random()) - (int)((maxValue+1)*Math.random());
        }
        return arr;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    //怎么设计这个对数器
    public static void main(String[] args) {
        int testTime = 200000;
        //一个数的右边数字有多少比我大的
        int maxValue = 100;//数组中每个数字1~100
        int maxSize = 100;//数组大小为1~100
        System.out.println("测试开始");
        for(int i =0;i<testTime;++i){
            int[] arr = generateRandomArray1(maxSize,maxValue);
            int[] arr1 = copyArray(arr);
            if(func(arr)!=BiggerThanRightTwice(arr1)){
                System.out.println("出错了");
                printArray(arr);
                printArray(arr1);
                break;
            }
        }
        System.out.println("测试结束");

    }


    public static void main2(String[] args) {
        int[] arr = {2,4,3,5,1};
        System.out.println(BiggerThanRightTwice(arr));//3
    }

}
